The present invention relates to cache invalidation techniques such as ones used by Web servers that supply information over the World Wide Web (“Web”).
Pages of information or other resources, such as images, sent, or transmitted, to a client from a Web server are typically stored in a Web cache once they are downloaded so that if a particular resource is requested a subsequent time, it can be re-presented to the client without the server having to be re-contacted. A familiar example of such an operation occurs when a PC user clicks on the “back” button of his Web browser, whereupon the browser retrieves a previously displayed page from a cache that may be maintained, for example, by the PC itself, by a proxy server to which the PC is connected via a local area network, or by an Internet service provider such as AT&T WorldNet Service.
Before delivering, or “serving,” a cached copy of a resource, a Web cache should ensure that it is consistent with (i.e., the same as) the copy then existing on the origin server, i.e., the server that had provided the resource. Otherwise, a client behind the cache may get a stale copy of the resource. If the origin server knows how long a resource will be good for (e.g., a daily newspaper generated each morning and deemed valid for 24 hours) it can provide the client with an explicit expiration time. If a user requests the resource after the expiration time, the client knows to ask the origin server for a fresh copy but otherwise it does not need to do so.
More commonly, however, the resource has no explicitly expressed expiration time, in which case there are two basic approaches for ensuring that an up-to-date copy of a resource is provided to the client.
The first approach is called client validation. The client treats a resource as potentially out-of-date on each request for the resource and sends to the origin server a cache validation request in the form of an If-Not-Modified header with each access. If the resource has not been modified since it was last sent to the requester, the server returns a so-called “304 Not Modified” status code response, thereby informing the requester that the cached copy is still good. This approach obviates the need for the server to re-transmit a resource that has not changed. However, it is still quite consumptive of Web resources; studies have shown that 20-30% of all requests on the Web are cache validation requests. Moreover, client validation can be quite inefficient if a resource is asked for a great deal but does not change often.
The second approach, referred to as server invalidation, addresses these concerns. Here, the origin server maintains, for one or more resources, a respective list of clients who requested that resource. The server takes on the responsibility of sending a so-called invalidation message to those clients when the resource in question changes, thereby letting them know that a newer version of the resource is available to be served from the server and that if the resource is again asked for by a user, an updated copy should thus be requested from the origin server because the resource has changed since it was served to the clients on the list. The server thereupon purges the client list, and then begins rebuilding it as subsequent requests come in for the resource in question. In the meantime, the server will have effectively made the clients aware that server invalidation is in effect for a resource by, for example, specifying an expiration time that is relatively far in the future, so that the clients will continue to use their cached copies until receiving an invalidation message. When an invalidation message is received by a client, the client flushes these items from its cache. Several protocols for sending such invalidation messages have been proposed See, for example, Balachander Krishnamurthy and Craig Wills, “Piggyback Server Invalidation for Proxy Cache Coherency,” Proceedings of the WWW-7 Conference, Brisbane, Australia, pp. 185-194, April 1998; Renu Tewari, Thirumale Niranjan, Srikanth Ramamurthy (IBM Research), “WCDP: A Protocol for Web Cache Consistency,” 7th International Workshop on Web Content Caching and Distribution (WCW); and John Dilley and Martin Arlitt and Stephane Perret and Tai Jin, “The Distributed Object Consistency Protocol,” Technical Report HPL-1999-109, Hewlett-Packard Labs, 1999.
Server invalidation greatly reduces the amount of Web traffic devoted to validation requests. However, it becomes unwieldy for a server when the number of clients on a list becomes very large because it results in a potentially inordinate amount of state maintenance on the part of the Web server. One solution for keeping the client list manageable is to implement server invalidation only for clients who are deemed “important” for one reason or another, such as clients who have explicitly subscribed to (and paid for) such a service. However, this leaves all other clients with having to issue client validation requests. Depending on the popularity of the resource, this could still result in a large volume of client validation requests and responses criss-crossing the Web, as well as consuming server resources.